Many types of data compression systems have been developed for use in various systems. Generally, data compression systems eliminate or reduce redundancies in the data of a file. Data compression systems are useful to represent information as accurately as possible with a minimum number of bits and thus minimize the amount of data which must be stored or transmitted in an information storage or transmission system. One way of doing this is to remove redundant information from the original data. A well-known compression technique is often referred to as zerotree compression.
In zerotree compression, a signal compression system applies a hierarchical subband decomposition, or wavelet transform, followed by a iterative successive approximation entropy-coded quantizer that incorporates zerotrees as discussed below. Wavelet transforms are used for low bit rate image compression because a wavelet transform leads to a hierarchical multi-scale representation of the source image. A significance map codes whether a coefficient in a discrete wavelet transform has a zero or nonzero quantized value. Typically, a large fraction of the bit budget for a computer system must be spent on encoding the significance map. Thus, a significant improvement in encoding the significance map translates into a significant improvement in the compression of information preparatory to storage or transmission.
One method of improving the encoding of a significance map is to define a data structure called a zerotree as known in the art. In zerotree encoding, a wavelet coefficient is said to be insignificant with respect to a given threshold T if the coefficient has a magnitude less than T. A wavelet coefficient that has a magnitude greater than or equal to T is said to be significant. Zerotree compression is based on the hypothesis that if a wavelet coefficient identified at a coarse frequency scale is insignificant with respect to a given threshold T, then all wavelet coefficients of the same orientation in the same spatial location at finer scales of the hierarchical subband decomposition are likely to be insignificant with respect to T. If this hypothesis is met, the identified wavelet coefficient is considered a zerotree root (zerotree).
More specifically, in a hierarchical subband system, with the exception of the highest frequency subbands, every coefficient at a given scale can be related to a set of coefficients at the next finer scale of similar orientation. The coefficient at the given scale is called the parent node, and all coefficients corresponding to the same spatial or temporal location at the next finer scale of similar orientation are called child nodes. For a given parent node, the set of all coefficients at all finer scales of similar orientation corresponding to the same location are called descendants. Similarly, for a given child node, the set of coefficients at all coarser scales of similar orientation corresponding to the same location are called ancestors. With the exception of the lowest frequency subband, all parent nodes have four child nodes. In the lowest frequency subband, the parent-child relationship is defined such that each parent node has three child nodes.
The scanning of the coefficients is performed such that no child node is scanned before any of its parent nodes. Given a threshold level to determine whether or not a coefficient is significant, a node is defined as a ZEROTREE ROOT if (1) the coefficient has an insignificant magnitude, (2) the node is not the descendant of a ZEROTREE ROOT, i.e., it is not completely predictable from a coarser scale, and (3) all of its descendants are insignificant. A ZEROTREE ROOT is encoded with a special symbol indicating that the insignificance of the coefficients at finer scales is completely predictable. To encode the binary significance map, three symbols are coded: ZEROTREES, ISOLATED ZEROS, and NON-ZEROS. In this zerotree system a static bit of coefficient indices is used and each coefficient is individually checked to determine whether (1) a symbol must be encoded or (2) it is completely predictable.
U.S. Pat. No. 5,412,741 to Shapiro ("Shapiro '741") discusses an improved zerotree system. In the Shapiro '741 system, for a given pass through the coefficients, a dominant list, used for storing coordinates of coefficients for coding, contains the coordinates of those coefficients for which one of the following two conditions apply: (1) the coefficient has not yet been found to be significant AND, a symbol will be generated on the CURRENT dominant pass, or (2) the coefficient has been previously found to be significant BUT one of its descendants satisfied condition (1).
The dominant list of Shapiro '741 excludes the coordinates of those coefficients which have not yet been found to be significant, but have ancestors that are zerotree roots. Given this condition, no symbol would be generated. However, under zerotree methods prior to Shapiro '741, this position would have to be checked to verify that some ancestor is a zerotree root. Shapiro '741 avoids wasting computation in checking the predictability of coefficients that are part of zerotrees, and thus predictably insignificant, by dynamically generating the dominant list during the dominant pass. The dominant pass is the part of iteration that discovers new coefficients significant with respect to the current threshold. At the beginning of a dominant pass, the dominant list contains the coordinates of all of the coefficients in the coarsest scale (lowest frequency) subband whether or not they have been previously found to be significant. As this list is scanned during a dominant pass, if a coefficient in the coarsest scale subband has not previously been found to be significant, then one of four symbols is encoded: (1) ISOLATED ZERO, (2) ZEROTREE ROOT, (3) POSITIVE SIGNIFICANT, (4) NEGATIVE SIGNIFICANT. Specifically, a ZEROTREE ROOT symbol is used when all of the descendants of the coefficient under consideration are either predictably insignificant, or have previously been found to be significant. In other words, a ZEROTREE ROOT implies that for all of the descendants, no symbol will be generated on the current dominant pass. In Shapiro '741, whenever a coefficient on the dominant list is not coded as a ZEROTREE ROOT, the dominant list for the current pass is appended to include the children of the current coefficient. Thus, the dominant list for the current pass will contain the coordinates of all coefficients that are not descendants of zerotrees, and thus Shapiro '741 states that the computational cost and compression time are improved.
While the system of Shapiro '741 offers computationally simple and efficient coding techniques, the time for encoding or decoding an image based on a wavelet transform can be further improved. One reason the speed of the system of Shapiro '741 can be improved is due to the Shapiro '741 system's use of arithmetic coding. The Shapiro '741 system is limited to an arithmetic coding due at least in part to very small size of the symbol set used to encode the coefficients. While Shapiro '741 specifies a certain symbol set based on certain rules for encoding coefficients, the Shapiro '741 symbol set limits efficient encoding to arithmetic coding. As known to those skilled in the art, arithmetic coding is most efficient when only a few symbols are to be used to encode coefficients, such as in Shapiro '741. Another reason the Shapiro '741 system is more suited for arithmetic coding is that Shapiro '741 only calculates a single threshold for evaluation against one bit plane before proceeding to evaluate the threshold against another bit plane. The Shapiro '741 symbol set and methodology of traversing and encoding trees of coefficients is not efficiently encoded by Huffman coding techniques.
Thus, there is a need in art for a coding system that is computational fast and efficient and that is operative for use with Huffman coding.